1. Field of the Invention
The present invention relates to the manipulation and control of data structures. More particularly the invention provides stack control through a plurality of individually addressable hardware registers used in combination with memory to provide multiple variable length stack frames.
2. Prior Art
The stack as a data structure where new data can be appended or data deleted is well known in the prior art. In block-oriented higher programming languages, such as PL1, PASCAL, Modula-two, and Ada, this data structure, which is known in these applications as run time stacks, is used to pass parameters at subroutine calls and to create a new generation of local variables for the called subroutine in addition to those variables generated by the calling routine. This new stack generated by the call is known as the activation record or stack frame. Parameters passed from the calling routine to the called subroutine may also be addressed as local variables from within the new stack relative to a frame pointer. The instruction counter, frame pointer and contents of the status register in the calling routine are stored at an address indicated by a stack pointer. The stack pointer indicates the end of a stack frame. A frame instruction increments the stack pointer as required by a new stack frame to accommodate the required local variables needed in the new stack frame. If necessary the frame pointer may be decremented to point to the beginning of the passed parameters.
A return instruction restores the old status by returning the frame pointer to the beginning of the old stack.
A typical implementation of a stack in memory as known in the prior art is shown in FIGS. 1A through 1D. FIG. 1A demonstrates the location of the frame pointer FP and stack pointer SP prior to a call for subroutine B. Included in the first stack frame defined by the frame pointer and stack pointer are memory locations defining parameter(s) for subroutine A at location 10. The status register for return from subroutine A is stored at location 12. The program counter for return from subroutine A is stored at location 14. The frame pointer for return from subroutine A is stored at location 16. The variables for subroutine A are stored at location(s) 18 and the parameters for subroutine B at location(s) 20.
A call of subroutine B is accomplished by storing the current status register at the address designated by the stack pointer, incrementing the stack pointer, storing the program counter at the location designated by the stack printer, incrementing the stack pointer and storing the frame pointer location at the location designated by the stack pointer, and again incrementing the stack pointer. The program counter is then set to the jump address and the frame pointer is set to the stack pointer. As shown in FIG. lB the status register for return from subroutine B is stored in location 22. The program counter for return from subroutine B is stored in location 24 and the frame pointer for return from subroutine B is stored in location 26. At the completion of these operations, the frame pointer and stack pointer are co-located at the next storage location.
To accommodate variables for subroutine B, a frame instruction is employed incrementing the stack counter by a number of bytes equal to the number of variables for frame B and decrementing the frame pointer by the number of parameter bytes for frame B. The resulting frame pointer and stack pointer locations after the frame instruction are shown in FIG. 1C.
Return from subroutine B is accomplished by decrementing the stack pointer by the number of bytes incremented for variable storage, setting the frame pointer equal to the value in the location addressed by the stack pointer, decrementing the stack pointer, setting the program counter equal to the value in the location designated by the stack pointer, decrementing the stack pointer, setting the status register equal to the value of the location designated by the stack pointer, and decrementing the stack pointer by the number of parameter bytes established for frame B. The final decrementing of the stack pointer may optionally exclude a number of return parameter bytes provided to the A subroutine. The status of the stack pointer and frame pointer after return is shown in FIG. 1D wherein location [SP] is the optional stack pointer location when return parameters are provided in location(s) 28.
The following definitions allow reduction of processing steps to equation form. Machine embodiments in the prior art and for the present invention to be subsequently described are based on a 32 bit architecture with bit 0 defined as the least significant and bit 31 as the most significant bit.
Operand [x . . y] denotes bits x through y of an operand. Example: MP[8 . . 2] denotes bits 8 through 2 of the memory pointer.
The symbol :=signifies the assignment symbol read as "is replaced by. " Expression denotes an operand which is addressed by the value of the expression. Depending on the context the expression addresses a memory location or a local register. For example, (SP) :=SR denotes replacement of the memory location designated by the value in the stack pointer with the value in the status register. &gt;,&gt;=, &lt;, denote the "greater than," "greater or equal," and "less than" relations.
In equation format the call, frame and return instructions of the prior art configurations are represented as:
______________________________________ Call B (SP) := SR; SP := SP+4; (SP) := PC; SP := SP+4; (SP) := FP; SP := SP+4; PC := jump-address FP := SP; Frame in B SP:= SP+n; FP := FP-p; n = number variable bytes for frame B p = number parameter bytes for frame B Return from B SP := SP-n; FP := (SP) , SP := SP-4; PC := (SP) ; SP := SP-4; SR := (SP) ; SP := SP-4-p+[r]; r = number return parameter bytes [r] is optional ______________________________________
A number of disadvantages exist in the prior art as described. Most notably, parameters must be stored on the stack by the calling routine and restored from the stack by the called subroutine. This requires double memory traffic due to the read/write requirements. In addition, many of the calling subroutine registers are normally saved on the stack either by the calling subroutine itself or by the called subroutine and then restored upon return. Again significant memory traffic is required.
The following modifications to the described "stack in memory" have been employed in the prior art singly or in combination:
1. The stack is addressed in descending order;
2. The status register is not saved when calling internal subroutines;
3. Past parameters are addressed through negative displacement relative to the frame pointer as opposed to decrementing the frame pointer;
4. The contents of the status register program counter and frame pointer are saved and restored in an alternate sequence;
5. The stack pointer designates the last valid value in the stack instead of the first unused address;
6. The local variables and past parameters are not addressed relative to the frame pointer but relative to the stack pointer allowing elimination of the frame pointer. However, this method has the additional disadvantage that an alteration of the stack pointer for storage of temporary results also changes the relative address.
7. The stack pointer is set to the value needed by the called subroutine by the calling routine eliminating the requirement for a frame instruction in the called subroutine. This method has the serious disadvantage that precompiled subroutines cannot be linked to calling routines without being recompiled to allow sequential adjustment of the stack frame length for the called subroutine in the calling routine.
Several prior art method and architectures exist to eliminate the disadvantages of the "stack in memory". In one such architecture the stack is implemented entirely in hardware through the use of registers in the CPU. This method is rarely employed since maximum stack size is severely limited by the available number of registers. Further, in a multi-tasking environment several stacks are required which must either be exchanged from memory or held in additional hardware register sets.
A second approach employs dividing the stack into a register part and a memory part. Only the top of the stack, that is, the recent or most recent stack frames, are held in registers while older stack frames are held in the memory part of the stack. If insufficient space exists in the register set when a new stack frame is created, the contents of the registers of the oldest register stack frame are stored into the memory part of the stack. The number of stored registers is required to be at least equal to the number of registers additionally required for the new stack frame. The memory address of the registers to be stored is held in a memory pointer which designates the upper most free address of the memory part of the stack. The memory pointer is incremented when registers are stored.
Operation of this mixed memory and register implementation is essentially the same as the standard method previously described with respect to FIGS. 1A through 1D; however, the following disadvantages are present. Three words for the status register program counter and frame pointer must be stored as return information by the call instruction into the stack registers and must be restored into the corresponding special registers (the status register, program counter and frame pointer register themselves) by a return instruction. Since typically only one arithmetic logic unit (ALU) is employed due to cost considerations, usually only one word per cycle may be transferred, thus requiring three cycles.
Further, variation 6 listed above may not be implemented since the frame pointer is required to check for underflow of the register portion of the stack on a return instruction.
In addition, to implement the mixed register and memory stack, a stack pointer which must be controlled by additional hardware is also necessary even though the most recent stack frame relative to the frame pointer can be addressed and treated like hardware registers. In a register-register architecture no stack is necessary for the computation of intermediate results such as parenthesis reduction and loops because intermediate results are not stored at the top of the stack but in explicitly denoted registers defined during compiling.
In a final implementation existing in the prior art a mixed memory and register configuration is again employed; however, single stack frames have fixed length. The number of past parameters and variables is fixed independent of the number actually required. Control of the stack is therefore very easy. The frame pointer is simply incremented at the call instruction or decremented at the return instruction and does not need to be stored. The stack pointer is also unnecessary and therefore omitted. The disadvantage of this elegant and simple method is the waste of unused registers. In order to provide sufficient registers for maximum stack size, average register use of approximately 50% results. This approach is highly discussed in the literature but rarely used in practice.